{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Operations to Halve Array Sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: halveArray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #将数组和减半的最少操作次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个正整数数组&nbsp;<code>nums</code>&nbsp;。每一次操作中，你可以从&nbsp;<code>nums</code>&nbsp;中选择 <strong>任意</strong>&nbsp;一个数并将它减小到 <strong>恰好</strong>&nbsp;一半。（注意，在后续操作中你可以对减半过的数继续执行操作）</p>\n",
    "\n",
    "<p>请你返回将 <code>nums</code>&nbsp;数组和 <strong>至少</strong>&nbsp;减少一半的 <strong>最少</strong>&nbsp;操作数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [5,19,8,1]\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>初始 nums 的和为 5 + 19 + 8 + 1 = 33 。\n",
    "以下是将数组和减少至少一半的一种方法：\n",
    "选择数字 19 并减小为 9.5 。\n",
    "选择数字 9.5 并减小为 4.75 。\n",
    "选择数字 8 并减小为 4 。\n",
    "最终数组为 [5, 4.75, 4, 1] ，和为 5 + 4.75 + 4 + 1 = 14.75 。\n",
    "nums 的和减小了 33 - 14.75 = 18.25 ，减小的部分超过了初始数组和的一半，18.25 &gt;= 33/2 = 16.5 。\n",
    "我们需要 3 个操作实现题目要求，所以返回 3 。\n",
    "可以证明，无法通过少于 3 个操作使数组和减少至少一半。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [3,8,20]\n",
    "<b>输出：</b>3\n",
    "<strong>解释：</strong>初始 nums 的和为 3 + 8 + 20 = 31 。\n",
    "以下是将数组和减少至少一半的一种方法：\n",
    "选择数字 20 并减小为 10 。\n",
    "选择数字 10 并减小为 5 。\n",
    "选择数字 3 并减小为 1.5 。\n",
    "最终数组为 [1.5, 8, 5] ，和为 1.5 + 8 + 5 = 14.5 。\n",
    "nums 的和减小了 31 - 14.5 = 16.5 ，减小的部分超过了初始数组和的一半， 16.5 &gt;= 31/2 = 15.5 。\n",
    "我们需要 3 个操作实现题目要求，所以返回 3 。\n",
    "可以证明，无法通过少于 3 个操作使数组和减少至少一半。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>7</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-operations-to-halve-array-sum](https://leetcode.cn/problems/minimum-operations-to-halve-array-sum/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-operations-to-halve-array-sum](https://leetcode.cn/problems/minimum-operations-to-halve-array-sum/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,19,8,1]', '[3,8,20]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        target = sum(nums) / 2\n",
    "        nums.sort()\n",
    "        deq = deque([nums[-1] / 2])\n",
    "        sub = deq[0]\n",
    "        nums.pop()\n",
    "        ans = 1\n",
    "        while sub < target:\n",
    "            if deq[0] > nums[-1]:\n",
    "                cur = deq.popleft() / 2\n",
    "            else:\n",
    "                cur = nums.pop() / 2\n",
    "            sub += cur\n",
    "            ans += 1\n",
    "            deq.append(cur)\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        target = sum(nums) / 2\n",
    "        nums.sort()\n",
    "        deq = deque([nums[-1] / 2])\n",
    "        sub = deq[0]\n",
    "        nums.pop()\n",
    "        ans = 1\n",
    "        while sub < target and nums:\n",
    "            if deq[0] > nums[-1]:\n",
    "                cur = deq.popleft() / 2\n",
    "            else:\n",
    "                cur = nums.pop() / 2\n",
    "            sub += cur\n",
    "            ans += 1\n",
    "            deq.append(cur)\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        total = sum(nums)\n",
    "        nums.sort()\n",
    "        deq = deque()\n",
    "        deq.append(nums[-1]/2)\n",
    "        ans = 1\n",
    "        sub = nums[-1]/2\n",
    "        nums.pop()\n",
    "        while sub < total/2 and nums:\n",
    "            if deq[0]> nums[-1]:\n",
    "                cur = deq.popleft()\n",
    "            else:\n",
    "                cur = nums.pop()\n",
    "            sub += cur/2\n",
    "            ans += 1\n",
    "            deq.append(cur/2)\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        total = sum(nums)\n",
    "        nums.sort()\n",
    "        deq = deque()\n",
    "        deq.append(nums[-1]/2)\n",
    "        ans = 1\n",
    "        sub = nums[-1]/2\n",
    "        nums.pop()\n",
    "        while sub < total/2 and nums:\n",
    "            if deq[0]> nums[-1]:\n",
    "                cur = deq.popleft()\n",
    "            else:\n",
    "                cur = nums.pop()\n",
    "            sub += cur/2\n",
    "            ans += 1\n",
    "            deq.append(cur/2)\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        total = sum(nums)\n",
    "        nums.sort()\n",
    "        queue = deque()\n",
    "        ans, sub = 0, 0\n",
    "        while sub < total / 2 and nums:\n",
    "            if queue and queue[0] > nums[-1]:\n",
    "                cur = queue.popleft()\n",
    "            else:\n",
    "                cur = nums.pop()\n",
    "            sub += cur / 2\n",
    "            ans += 1\n",
    "            queue.append(cur / 2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        heap = []\n",
    "        heapsum = 0\n",
    "        while nums:\n",
    "            temp = nums.pop()\n",
    "            heapsum += temp\n",
    "            self.heapInsert(heap, temp)\n",
    "        halfsum = heapsum / 2\n",
    "        count = 0\n",
    "        while heapsum > halfsum:\n",
    "            val = self.heapDelete(heap)\n",
    "            self.heapInsert(heap, val/2)\n",
    "            heapsum -= val/2\n",
    "            count += 1\n",
    "        return count\n",
    "        \n",
    "    def heapInsert(self, heap, val):\n",
    "        heap.append(val)\n",
    "        i = len(heap) - 1\n",
    "        while i > 0 and heap[i] > heap[(i-1)//2]:\n",
    "            self.swap(heap, i, (i-1)//2)\n",
    "            i = (i-1)//2\n",
    "    \n",
    "    def swap(self, heap, i, j):\n",
    "        temp = heap[i]\n",
    "        heap[i] = heap[j]\n",
    "        heap[j] = temp\n",
    "\n",
    "    def heapDelete(self, heap):\n",
    "        k = len(heap)-1\n",
    "        self.swap(heap, 0, k)\n",
    "        val = heap.pop()\n",
    "        k -= 1\n",
    "        i = 0\n",
    "        while 2*i+1 <= k:\n",
    "            if 2*i+2 <=k and heap[2*i+1] < heap[2*i+2]:\n",
    "                best = 2*i+2\n",
    "            else:\n",
    "                best = 2*i+1\n",
    "            if heap[i] < heap[best]:\n",
    "                self.swap(heap, i, best)\n",
    "                i = best\n",
    "            else:\n",
    "                break\n",
    "        return val\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "            cnt = 0\n",
    "            a=[]\n",
    "            index=0\n",
    "            b = 0\n",
    "            nums.sort()\n",
    "            mid = sum(nums) / 2\n",
    "            while b < mid:\n",
    "                if len(a)==0 or  nums[-1]>=a[index]:\n",
    "                    value=nums[-1]/2\n",
    "                    b += value\n",
    "                    nums.pop()\n",
    "                    a.append(value)\n",
    "                else:\n",
    "                    value=a[index]/2\n",
    "                    b+=value\n",
    "                    index+=1\n",
    "                    a.append(value)\n",
    "            return len(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# import time\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        # t1 = time.time()\n",
    "        tot = sum(nums)\n",
    "        nums.sort()\n",
    "        require = tot / 2\n",
    "        cur = 0\n",
    "        ans = 0\n",
    "        a = 0\n",
    "        arr = SortedList()\n",
    "        # while cur < require:\n",
    "        #     a = nums.pop()\n",
    "        #     cur +=  a / 2\n",
    "        #     bisect.insort_left(nums, a / 2)\n",
    "        #     ans += 1\n",
    "        \n",
    "        while cur < require:\n",
    "            if not arr:\n",
    "                a = nums.pop()\n",
    "            else:\n",
    "                if arr[-1] > nums[-1]:\n",
    "                    a = arr.pop()\n",
    "                else:\n",
    "                    a = nums.pop()\n",
    "            b = a / 2\n",
    "            cur += b\n",
    "            arr.add(b)\n",
    "            ans += 1                    \n",
    "            \n",
    "        # print(time.time() - t1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        from heapq import heapify\n",
    "        nums.sort(reverse=True)\n",
    "        a = sum(nums)\n",
    "        i = 0        \n",
    "        m= a\n",
    "        nums = [-i for i in nums]\n",
    "        heapq.heapify(nums)\n",
    "        while m>a/2:\n",
    "            tmp = heappop(nums)\n",
    "            m +=tmp/2\n",
    "            heappush(nums,tmp/2)\n",
    "            i+=1\n",
    "            \n",
    "        return i\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        from sortedcontainers import SortedList\n",
    "\n",
    "        sl = SortedList(nums)\n",
    "        su = sum(nums)\n",
    "        cnt = 0\n",
    "        ans = 0\n",
    "        while cnt < su / 2:\n",
    "            a = sl.pop()\n",
    "            a /= 2\n",
    "            cnt += a\n",
    "            sl.add(a)\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        from heapq import heapify\n",
    "        nums.sort(reverse=True)\n",
    "        a = sum(nums)\n",
    "        b = 0\n",
    "        i = 0\n",
    "        print(nums)\n",
    "        \n",
    "        m= a\n",
    "        nums = [-i for i in nums]\n",
    "        heapq.heapify(nums)\n",
    "        while m>a/2:\n",
    "            tmp = heappop(nums)\n",
    "            m +=tmp/2\n",
    "            heappush(nums,tmp/2)\n",
    "            i+=1\n",
    "            \n",
    "        return i\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        nums.sort()  \n",
    "        target = sum(nums)/2 \n",
    "        res=0 \n",
    "        pq=[]\n",
    "\n",
    "        while target > 0:\n",
    "            if not pq or nums[-1] > -pq[0]:\n",
    "                n = nums.pop()\n",
    "                target -= n/2\n",
    "                res += 1\n",
    "                pq.append(-n/2)\n",
    "            else:\n",
    "                n = -heappop(pq)\n",
    "                target -= n/2\n",
    "                res += 1\n",
    "                pq.append(-n/2)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "            a=[]\n",
    "            index=0\n",
    "            b = 0\n",
    "            nums.sort()\n",
    "            mid = sum(nums) / 2\n",
    "            while b < mid:\n",
    "                if len(a)==0 or  nums[-1]>=a[index]:\n",
    "                    value=nums[-1]/2\n",
    "                    b += value\n",
    "                    nums.pop()\n",
    "                    a.append(value)\n",
    "                else:\n",
    "                    value=a[index]/2\n",
    "                    b+=value\n",
    "                    index+=1\n",
    "                    a.append(value)\n",
    "            return len(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        nums.sort()  \n",
    "        target = sum(nums)/2 \n",
    "        res=0 \n",
    "        pq=[]\n",
    "\n",
    "        # while target > 0:\n",
    "        #     if not pq or nums[-1] > pq[0]:\n",
    "        #         n = nums.pop()\n",
    "        #         target -= n/2\n",
    "        #         res += 1\n",
    "        #         heappush(pq,n/2)\n",
    "        #     else:\n",
    "        #         n = heappop(pq)\n",
    "        #         target -= n/2\n",
    "        #         res += 1\n",
    "        #         heappush(pq,n/2)\n",
    "        # return res\n",
    "\n",
    "        while target >0 :\n",
    "            if not pq or nums[-1] > -pq[0]:\n",
    "                n = nums.pop()\n",
    "                target -= n/2\n",
    "                res += 1\n",
    "                heappush(pq,-n/2)\n",
    "            else:\n",
    "                n = -heappop(pq)\n",
    "                target -= n/2\n",
    "                res += 1\n",
    "                heappush(pq,-n/2)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 那肯定每次都选最大的.. 保持有序\n",
    "# 减半之后二分插入进去就好\n",
    "\n",
    "# 这样竟然会爆时间复杂度 nlgn 如何降低呢\n",
    "# 开一个大根堆保存最大的2个 每次检查堆顶除以2 若小于原始队列最大的 那么原始队列进多一个元素进堆\n",
    "# 这样时间复杂度应该比lgn小\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 1:\n",
    "            return 1\n",
    "        target = sum(nums) / 2\n",
    "        nums.sort()\n",
    "        t, res = 0, 0\n",
    "        heap = []\n",
    "        for i in range(2):\n",
    "            heapq.heappush(heap, -nums.pop())\n",
    "        while t < target:\n",
    "            n = -heapq.heappop(heap) / 2\n",
    "            res += 1\n",
    "            t += n\n",
    "            if nums and n <= nums[-1]:\n",
    "                heapq.heappush(heap, -nums.pop())\n",
    "            heapq.heappush(heap, -n)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 那肯定每次都选最大的.. 保持有序\n",
    "# 减半之后二分插入进去就好\n",
    "\n",
    "# 这样竟然会爆时间复杂度 nlgn 如何降低呢\n",
    "# 开一个大根堆保存最大的2个 每次检查堆顶除以2 若小于原始队列最大的 那么原始队列进多一个元素进堆\n",
    "# 这样时间复杂度应该比lgn小\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 1:\n",
    "            return 1\n",
    "        target = sum(nums) / 2\n",
    "        nums.sort()\n",
    "        t, res = 0, 0\n",
    "        heap = []\n",
    "        for i in range(2):\n",
    "            heapq.heappush(heap, -nums.pop())\n",
    "        while t < target:\n",
    "            n = -heapq.heappop(heap) / 2\n",
    "            res += 1\n",
    "            t += n\n",
    "            if nums and n <= nums[-1]:\n",
    "                heapq.heappush(heap, -nums.pop())\n",
    "            heapq.heappush(heap, -n)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            nums[i] = -(nums[i] << 20)\n",
    "        # 创建大根堆\n",
    "        heapify(nums)\n",
    "        ans = 0\n",
    "        half = sum(nums) >> 1\n",
    "        while half < 0:\n",
    "            half -= nums[0] >> 1\n",
    "            heapreplace(nums, nums[0] >> 1)\n",
    "            ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            nums[i] = -(nums[i] << 20)\n",
    "        heapify(nums)\n",
    "        ans = 0\n",
    "        half = sum(nums) >> 1\n",
    "        while half < 0:\n",
    "            half -= nums[0] >> 1\n",
    "            heapreplace(nums, nums[0] >> 1)\n",
    "            ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            nums[i] = -(nums[i] << 20)\n",
    "        heapify(nums)\n",
    "        ans = 0\n",
    "        half = sum(nums) >> 1\n",
    "        while half < 0:\n",
    "            half -= nums[0] >> 1\n",
    "            heapreplace(nums, nums[0] >> 1)\n",
    "            ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            nums[i] = -(nums[i]<<20)\n",
    "        heapq.heapify(nums)\n",
    "        total = sum(nums) >> 1\n",
    "        res = 0\n",
    "        while total < 0:\n",
    "            total -= nums[0] >> 1\n",
    "            heapq.heapreplace(nums, nums[0]>>1)\n",
    "            res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        '''\n",
    "        arr = [-v for v in nums]\n",
    "        heapq.heapify(arr)\n",
    "        res = sum(nums) / 2.0\n",
    "        cur = 0\n",
    "        steps = 0\n",
    "        while cur < res:\n",
    "            v = heapq.heappop(arr)\n",
    "            v = -v\n",
    "            cur += v / 2.0\n",
    "            heapq.heappush(arr, -v / 2.0)\n",
    "            steps += 1\n",
    "        return steps\n",
    "        '''\n",
    "        for i in range(len(nums)):\n",
    "            nums[i] = -(nums[i] << 20)\n",
    "        heapq.heapify(nums)\n",
    "        \n",
    "        ans = 0\n",
    "        half = sum(nums) >> 1\n",
    "        while half < 0:\n",
    "            half -= nums[0] >> 1\n",
    "            heapq.heapreplace(nums, nums[0] >> 1)\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        l = len(nums)\n",
    "        _m = l\n",
    "        a = list(map(lambda x:-x,nums))\n",
    "        heapq.heapify(a)\n",
    "        count = 0\n",
    "        s = sum(a)\n",
    "        print(f\"a: {a} s: {s}\")\n",
    "        cur = 0\n",
    "        while count < _m:\n",
    "            c = heappop(a)\n",
    "    \n",
    "            cur += c/2\n",
    "            # print(f\"cur: {cur} s/2: {s/2}\")\n",
    "            if cur <= s/2:\n",
    "                return count + 1\n",
    "            else:\n",
    "                heappush(a, c/2)\n",
    "            count += 1\n",
    "        return count\n",
    "                \n",
    "            \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    class MaxHeap(object):\n",
    "        def __init__(self, array):\n",
    "            self.array = []\n",
    "            for index in range((len(array)-1)//2, -1, -1):\n",
    "                self.sink(index, array)\n",
    "\n",
    "        def __str__(self):\n",
    "            return str(self.array)\n",
    "\n",
    "        def __len__(self):\n",
    "            return len(self.array)\n",
    "\n",
    "        # index的参数都是len(self.array)\n",
    "        def insert(self, num, index):\n",
    "            self.array.append(num)\n",
    "            # 拿到父节点的索引\n",
    "            parent_index = index // 2\n",
    "            while parent_index >= 0 and self.array[parent_index] < num:\n",
    "                # 对换和父节点的位置\n",
    "                self.array[parent_index], self.array[index] = self.array[index], self.array[parent_index]\n",
    "                # 如果已经是根节点则退出循环\n",
    "                if parent_index == 0:\n",
    "                    break\n",
    "                index = parent_index\n",
    "                parent_index = parent_index // 2\n",
    "\n",
    "        def sink(self, index, array):\n",
    "            left_node_index = 2 * index + 1\n",
    "            right_node_index = 2 * index + 2\n",
    "            # 如果左节点的索引小于数组的长度则说明有左节点\n",
    "            if left_node_index < len(array):\n",
    "                left_v = array[left_node_index]\n",
    "                if right_node_index >= len(array):\n",
    "                    max_value = left_v\n",
    "                    max_index = left_node_index\n",
    "                else:\n",
    "                    right_v = array[right_node_index]\n",
    "                    if left_v < right_v:\n",
    "                        max_value = right_v\n",
    "                        max_index = right_node_index\n",
    "                    else:\n",
    "                        max_value = left_v\n",
    "                        max_index = left_node_index\n",
    "                if array[index] < max_value:\n",
    "                    array[index], array[max_index] = array[max_index], array[index]\n",
    "                    self.sink(max_index, array)\n",
    "            self.array = array\n",
    "\n",
    "        def pop(self):\n",
    "            end_v = self.array.pop()\n",
    "            if len(self.array) == 0:\n",
    "                return end_v\n",
    "            max_value = self.array[0]\n",
    "            self.array[0] = end_v\n",
    "            self.sink(0, self.array)\n",
    "            return max_value\n",
    "\n",
    "\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        s = sum(nums)/2\n",
    "        maxheap = self.MaxHeap(nums)\n",
    "        count = 0\n",
    "        while s>0:\n",
    "            count = count + 1\n",
    "            max_num = maxheap.pop()/2\n",
    "            s = s - max_num\n",
    "            maxheap.insert(max_num, len(maxheap))\n",
    "        return count\n",
    "\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            nums[i] = -(nums[i] << 20)\n",
    "        heapify(nums)\n",
    "        ans = 0\n",
    "        half = sum(nums) >> 1\n",
    "        while half < 0:\n",
    "            half -= nums[0] >> 1\n",
    "            heapreplace(nums, nums[0] >> 1)\n",
    "            ans += 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "# 作者：endlesscheng\n",
    "# 链接：https://leetcode-cn.com/problems/minimum-operations-to-halve-array-sum/solution/by-endlesscheng-xzk2/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            nums[i] = -(nums[i] << 20)\n",
    "        heapify(nums)\n",
    "        ans = 0\n",
    "        half = sum(nums) >> 1\n",
    "        while half < 0:\n",
    "            half -= nums[0] >> 1\n",
    "            heapreplace(nums, nums[0] >> 1)\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        import heapq\n",
    "        heap=[]\n",
    "        sum=0\n",
    "        for num in nums:\n",
    "            sum+=num\n",
    "            num=-num\n",
    "            heapq.heappush(heap,num)\n",
    "        print(sum,heap)\n",
    "        sum_tmp=sum\n",
    "        cnt=0\n",
    "        while heap:\n",
    "            tmp=-heapq.heappop(heap)\n",
    "            # print(tmp)\n",
    "            heapq.heappush(heap,-float(tmp/2))\n",
    "            # print(heap)\n",
    "            cnt+=1\n",
    "            sum_tmp-=float(tmp/2)\n",
    "            if sum_tmp<=float(sum/2):\n",
    "                return cnt\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        \n",
    "        cnt, sum1 = 0, sum(nums) / 2\n",
    "        nums.sort()\n",
    "        while True:\n",
    "            if nums[-1] <= nums[0] << 1: \n",
    "                for x in nums[::-1]:\n",
    "                    sum1 -= x / 2 \n",
    "                    cnt += 1\n",
    "                    if sum1 <= 0: return cnt\n",
    "            else:                \n",
    "                sum1 -= (tmp := nums.pop() / 2)\n",
    "                cnt += 1\n",
    "                if sum1 <= 0: return cnt\n",
    "                i = bisect.bisect_left(nums, tmp)\n",
    "                nums.insert(i, tmp)\n",
    "            #print(cnt, sum1, nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "\n",
    "        # 时间复杂度：O(nlog⁡n)\n",
    "        # #空间复杂度：O(1)\n",
    "        # for i in range(len(nums)):\n",
    "        #     nums[i] = -(nums[i]<<20)  # 取负号变最大堆\n",
    "        # heapify(nums)   #将list转换成堆\n",
    "        # ans = 0\n",
    "        # half = sum(nums)>>1\n",
    "        # while half<0:\n",
    "        #     half -= nums[0]>>1\n",
    "        #     heapreplace(nums,nums[0]>>1)   #先取出最小的一项在放入计算好的，最小就是换号后最大的\n",
    "        #     ans +=1\n",
    "        # return ans\n",
    "\n",
    "        # pq = []\n",
    "        # for num in nums:\n",
    "        #     heappush(pq, -num)\n",
    "        # res = 0\n",
    "        # sum1 = sum(nums)\n",
    "        # sum2 = 0\n",
    "        # return sum1\n",
    "        # while sum2 < sum1 / 2:\n",
    "        #     x = -heappop(pq)  #取正\n",
    "        #     sum2 += x / 2\n",
    "        #     heappush(pq, -(x / 2))\n",
    "        #     res += 1\n",
    "        # return res\n",
    "\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            nums[i] = -(nums[i]<<2)\n",
    "        heapify(nums)\n",
    "        res = 0\n",
    "        half = sum(nums)>>1\n",
    "        while half < 0:\n",
    "            half -= nums[0]>>1\n",
    "            # heapreplace(nums,nums[0]>>1)\n",
    "            heappushpop(nums,nums[0]>>1)\n",
    "            res += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        target = sum(nums) / 2\n",
    "        result = 0\n",
    "        nums.sort()\n",
    "\n",
    "        while target > 0:\n",
    "            target -= nums[-1] / 2\n",
    "            bisect.insort(nums, nums.pop() / 2)\n",
    "            result += 1\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        def heapify(nums, i):\n",
    "            l = 2 * i + 1\n",
    "            r = 2 * i + 2\n",
    "            index = i\n",
    "            if l < len(nums) and nums[l] > nums[index]:\n",
    "                index = l\n",
    "            if r < len(nums) and nums[r] > nums[index]:\n",
    "                index = r\n",
    "            if index != i:\n",
    "                nums[i], nums[index] = nums[index], nums[i]\n",
    "                heapify(nums, index)\n",
    "            return\n",
    "\n",
    "        n, half_sum = len(nums), sum(nums) / 2\n",
    "        for i in range(n // 2, -1, -1):\n",
    "            heapify(nums, i)\n",
    "        cur_sum, cnt = 0, 0\n",
    "        while cur_sum < half_sum:\n",
    "            nums[0] /= 2\n",
    "            cur_sum += nums[0]\n",
    "            cnt += 1\n",
    "            heapify(nums, 0)\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int: \n",
    "\n",
    "        total = sum(nums) \n",
    "        half = total/2 \n",
    "        # print(total, half) \n",
    "\n",
    "        # 堆 heap \n",
    "        \n",
    "        # 构建最大堆，因为 Python 中只有最小堆，因为需要取反\n",
    "        for i in range(len(nums)): \n",
    "            nums[i] = -nums[i] \n",
    "        # print(nums)\n",
    "        heapq.heapify(nums)  \n",
    "\n",
    "        count = 0\n",
    "        while total > half: \n",
    "            max_value = heapq.heappop(nums)/2  # pop 出的堆顶元素是负数\n",
    "            total -= -max_value\n",
    "            heapq.heappush(nums, max_value) \n",
    "            count += 1\n",
    "            # print(max_value, nums, total, count) \n",
    "        return count  \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        class PriorQueue:\n",
    "            def __init__(self, lst):\n",
    "                self.elems = lst\n",
    "                self.build_heap()\n",
    "\n",
    "            def heapify(self, e, beg, end):\n",
    "                i = beg\n",
    "                j = 2*beg+1\n",
    "                while j<=end:\n",
    "                    if j+1<=end and self.elems[j+1]>self.elems[j]:\n",
    "                        j = j+1\n",
    "                    if e>=self.elems[j]:\n",
    "                        break\n",
    "                    self.elems[i] = self.elems[j]\n",
    "                    i = j\n",
    "                    j = 2*i+1\n",
    "                self.elems[i] = e\n",
    "\n",
    "            def heap_modify(self):\n",
    "                self.elems[0] = self.elems[0]/2\n",
    "                p = self.elems[0]\n",
    "                self.heapify(self.elems[0], 0, len(self.elems)-1)\n",
    "                return p\n",
    "\n",
    "            def build_heap(self):\n",
    "                for i in range(len(self.elems)-1, -1, -1):\n",
    "                    self.heapify(self.elems[i], i, len(self.elems)-1)\n",
    "            \n",
    "        cur_sum = sum(nums)\n",
    "        target = cur_sum/2\n",
    "        ans = 0\n",
    "        pq = PriorQueue(nums)\n",
    "        while cur_sum>target:\n",
    "            p = pq.heap_modify()\n",
    "            cur_sum -= p\n",
    "            ans += 1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        class PriorQueue:\n",
    "            def __init__(self, lst):\n",
    "                self.elems = lst\n",
    "                self.build_heap()\n",
    "\n",
    "            def heapify(self, e, beg, end):\n",
    "                i = beg\n",
    "                j = 2*beg+1\n",
    "                while j<=end:\n",
    "                    if j+1<=end and self.elems[j+1]>self.elems[j]:\n",
    "                        j = j+1\n",
    "                    if e>self.elems[j]:\n",
    "                        break\n",
    "                    self.elems[i] = self.elems[j]\n",
    "                    i = j\n",
    "                    j = 2*i+1\n",
    "                self.elems[i] = e\n",
    "            \n",
    "            def heap_modify(self):\n",
    "                self.elems[0] = self.elems[0]/2\n",
    "                p = self.elems[0]\n",
    "                self.heapify(self.elems[0], 0, len(self.elems)-1)\n",
    "                return p\n",
    "\n",
    "            def build_heap(self):\n",
    "                for i in range(len(self.elems)-1, -1, -1):\n",
    "                    self.heapify(self.elems[i], i, len(self.elems)-1)\n",
    "            \n",
    "        cur_sum = sum(nums)\n",
    "        target = cur_sum/2\n",
    "        ans = 0\n",
    "        pq = PriorQueue(nums)\n",
    "        while cur_sum>target:\n",
    "            p = pq.heap_modify()\n",
    "            cur_sum -= p\n",
    "            ans += 1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        total = sum(nums)\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            nums[i] = -nums[i]\n",
    "        heapq.heapify(nums)\n",
    "        dec = 0\n",
    "        res = 0\n",
    "        while dec < total / 2:\n",
    "            opt = heapq.heappop(nums)\n",
    "            dec += -opt / 2\n",
    "            res += 1\n",
    "            heapq.heappush(nums, opt / 2)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        heap = [0] * len(nums)\n",
    "        heapsum = 0\n",
    "        for i in range(len(nums)-1, -1, -1):\n",
    "            temp = nums[i]<<20\n",
    "            heapsum += temp\n",
    "            heap[i] = temp\n",
    "            self.heapify(heap, i)\n",
    "        halfsum = heapsum / 2\n",
    "        count = 0\n",
    "        while heapsum > halfsum:\n",
    "            temp = heap[0]/2\n",
    "            heap[0] = temp\n",
    "            heapsum -= temp\n",
    "            self.heapify(heap, 0)\n",
    "            count += 1\n",
    "        return count\n",
    "    \n",
    "    def swap(self, heap, i, j):\n",
    "        temp = heap[i]\n",
    "        heap[i] = heap[j]\n",
    "        heap[j] = temp\n",
    "\n",
    "    def heapify(self, heap, i):\n",
    "        k = len(heap)-1\n",
    "        while 2*i+1 <= k:\n",
    "            if 2*i+2 <=k and heap[2*i+1] < heap[2*i+2]:\n",
    "                best = 2*i+2\n",
    "            else:\n",
    "                best = 2*i+1\n",
    "            if heap[i] < heap[best]:\n",
    "                self.swap(heap, i, best)\n",
    "                i = best\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        from heapq import _heapify_max as heapify\n",
    "        from heapq import _heappop_max as heappop\n",
    "        from heapq import _heapreplace_max as heappush\n",
    "        total = sum(nums)\n",
    "        heapify(nums)\n",
    "        cur = 0\n",
    "        cnt = 0\n",
    "        while cur * 2 < total:\n",
    "            # print(cnt,cur,nums)\n",
    "            tmp = nums[0]\n",
    "            heappush(nums,tmp/2)\n",
    "            cur += tmp/2\n",
    "            cnt +=1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        heap = [0] * len(nums)\n",
    "        heapsum = 0\n",
    "        for i in range(len(nums)-1, -1, -1):\n",
    "            temp = nums[i]<<20\n",
    "            heapsum += temp\n",
    "            heap[i] = temp\n",
    "            self.heapify(heap, i)\n",
    "        halfsum = heapsum / 2\n",
    "        count = 0\n",
    "        while heapsum > halfsum:\n",
    "            temp = int(heap[0]/2)\n",
    "            heap[0] = temp\n",
    "            heapsum -= temp\n",
    "            self.heapify(heap, 0)\n",
    "            count += 1\n",
    "        return count\n",
    "    \n",
    "    def swap(self, heap, i, j):\n",
    "        temp = heap[i]\n",
    "        heap[i] = heap[j]\n",
    "        heap[j] = temp\n",
    "\n",
    "    def heapify(self, heap, i):\n",
    "        k = len(heap)-1\n",
    "        while 2*i+1 <= k:\n",
    "            if 2*i+2 <=k and heap[2*i+1] < heap[2*i+2]:\n",
    "                best = 2*i+2\n",
    "            else:\n",
    "                best = 2*i+1\n",
    "            if heap[i] < heap[best]:\n",
    "                self.swap(heap, i, best)\n",
    "                i = best\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return 1\n",
    "\n",
    "        t, d = sum(nums)/2, 0\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            nums[i] = -nums[i]\n",
    "\n",
    "        heapq.heapify(nums)\n",
    "        while d < t:\n",
    "            num = heapq.heappop(nums)\n",
    "            d -= num/2\n",
    "            heapq.heappush(nums, num/2)\n",
    "            ans += 1\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        s = sum(nums) / 2\n",
    "        h = []\n",
    "        for v in nums:\n",
    "            heappush(h, -v)\n",
    "        ans = 0\n",
    "        while s > 0:\n",
    "            t = -heappop(h) / 2\n",
    "            s -= t\n",
    "            heappush(h, -t)\n",
    "            ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Heap:\n",
    "    def __init__(self, nums: list[int]) -> None:\n",
    "        self.nums = []\n",
    "        if nums:\n",
    "            self.nums.append(nums[0])\n",
    "            for i in range(1, len(nums)):\n",
    "                self.insert(nums[i])\n",
    "\n",
    "    def insert(self, content: int) -> None:\n",
    "        self.nums.append(content)\n",
    "        x = len(self.nums)-1\n",
    "        while x != 0 and self.nums[x] > self.nums[(x+1)//2-1]:\n",
    "            tmp = self.nums[x]\n",
    "            self.nums[x] = self.nums[(x+1)//2-1]\n",
    "            self.nums[(x+1)//2-1] = tmp\n",
    "            x = (x+1)//2-1\n",
    "\n",
    "    def pop(self) -> int:\n",
    "        tmp = self.nums[0]\n",
    "        self.nums[0] = self.nums[-1]\n",
    "        self.nums[-1] = tmp\n",
    "        r = self.nums.pop()\n",
    "        x = 0\n",
    "        while True:\n",
    "            if 2*x+1 >= len(self.nums):\n",
    "                left = -math.inf\n",
    "            else:\n",
    "                left = self.nums[2*x+1]\n",
    "            if 2*(x+1) >= len(self.nums):\n",
    "                right = -math.inf\n",
    "            else:\n",
    "                right = self.nums[2*(x+1)]           \n",
    "            if left == right == -math.inf:\n",
    "                break\n",
    "            elif max(left, right) > self.nums[x]:\n",
    "                if left > right:\n",
    "                    tmp = self.nums[x]\n",
    "                    self.nums[x] = self.nums[2*x+1]\n",
    "                    self.nums[2*x+1] = tmp\n",
    "                    x = 2*x+1\n",
    "                else:\n",
    "                    tmp = self.nums[x]\n",
    "                    self.nums[x] = self.nums[2*(x+1)]\n",
    "                    self.nums[2*(x+1)] = tmp\n",
    "                    x = 2*(x+1)\n",
    "            else:\n",
    "                break\n",
    "        return r\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: list[int]) -> int:\n",
    "        pq = Heap(nums)\n",
    "        res = 0\n",
    "        sum1 = sum(nums)\n",
    "        sum2 = 0\n",
    "        while sum2 < sum1 / 2:\n",
    "            x = pq.pop()\n",
    "            sum2 += x / 2\n",
    "            pq.insert(x / 2)\n",
    "            res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import insort_right\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        sums = sum(nums)\n",
    "        nums.sort()\n",
    "        new_sums = sums\n",
    "        cz = 0\n",
    "        while new_sums > sums/2:\n",
    "            maxi = nums.pop()\n",
    "            \n",
    "            new_sums -= maxi/2\n",
    "            # nums.append(maxi/2)\n",
    "            # nums.sort()\n",
    "\n",
    "            insort_right(nums, maxi/2)\n",
    "            cz += 1\n",
    "        return cz\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        temp=sum(nums)/2\n",
    "        res=[]\n",
    "        ans=0\n",
    "        for i in nums:\n",
    "            heapq.heappush(res,-i)\n",
    "        while temp>0:\n",
    "            t=-heapq.heappop(res)/2\n",
    "            temp-=t\n",
    "            heapq.heappush(res,-t)\n",
    "            ans+=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        _sum = sum(nums)\n",
    "        def check(t):\n",
    "            pq = [-x for x in nums]\n",
    "            heapify(pq)\n",
    "            a = 0\n",
    "            while t > 0:\n",
    "                cur = heappop(pq)/2\n",
    "                a += -cur\n",
    "                if a*2 >= _sum:\n",
    "                    return True\n",
    "                t -= 1\n",
    "                heappush(pq,cur)\n",
    "            return False\n",
    "\n",
    "        l,r = 0,n + 1\n",
    "        while l + 1 < r:\n",
    "            mid = (l + r) >> 1\n",
    "            if check(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        class PriorQueue:\n",
    "            def __init__(self, lst):\n",
    "                self.elems = lst\n",
    "                self.build_heap()\n",
    "\n",
    "            def heapify(self, e, beg, end):\n",
    "                i = beg\n",
    "                j = 2*beg+1\n",
    "                while j<=end:\n",
    "                    if j+1<=end and self.elems[j+1]>self.elems[j]:\n",
    "                        j = j+1\n",
    "                    if e>=self.elems[j]:\n",
    "                        break\n",
    "                    self.elems[i] = self.elems[j]\n",
    "                    i = j\n",
    "                    j = 2*i+1\n",
    "                self.elems[i] = e\n",
    "\n",
    "            def heap_modify(self):\n",
    "                self.elems[0] = self.elems[0]//2\n",
    "                p = self.elems[0]\n",
    "                self.heapify(self.elems[0], 0, len(self.elems)-1)\n",
    "                return p\n",
    "\n",
    "            def build_heap(self):\n",
    "                for i in range(len(self.elems)-1, -1, -1):\n",
    "                    self.heapify(self.elems[i], i, len(self.elems)-1)\n",
    "        nums = [num*2**10 for num in nums]\n",
    "        cur_sum = sum(nums)\n",
    "        target = cur_sum//2\n",
    "        ans = 0\n",
    "        pq = PriorQueue(nums)\n",
    "        while cur_sum>target:\n",
    "            p = pq.heap_modify()\n",
    "            cur_sum -= p\n",
    "            ans += 1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        q=[]\n",
    "        for x in nums:\n",
    "          heapq.heappush(q,-x)  \n",
    "        print(q)\n",
    "        s=sum(nums)/2\n",
    "        c=0\n",
    "        while s>0:\n",
    "           e=-heapq.heappop(q)\n",
    "           s-=e/2\n",
    "           heapq.heappush(q,-e/2)\n",
    "           c+=1\n",
    "        return c    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        nums = SortedList(nums)\n",
    "        Sum = sum(nums) / 2\n",
    "        total = 0\n",
    "        cnt = 0\n",
    "        while total < Sum:\n",
    "            last = nums.pop() / 2\n",
    "            nums.add(last)\n",
    "            total += last\n",
    "            cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import *\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        s = 0\n",
    "        heap = []\n",
    "        for n in nums:\n",
    "            s += n\n",
    "            heappush(heap, -n)\n",
    "        \n",
    "        cnt = 0\n",
    "        target = s / 2\n",
    "        while s > target:\n",
    "            cnt += 1\n",
    "            n = -heappop(heap)\n",
    "            n /= 2\n",
    "            s -= n\n",
    "            heappush(heap, -n)\n",
    "        return cnt\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        sum0 = sum(nums)\n",
    "        cutsum = 0\n",
    "        time  = 0\n",
    "        shouldbreak = False\n",
    "        while True:\n",
    "            nums.sort()\n",
    "            halfbest = nums[-1]/2\n",
    "            for i in range(len(nums)-1,-1,-1):\n",
    "                if nums[i] >= halfbest:\n",
    "                    nums[i] = nums[i]/2\n",
    "                    cutsum += nums[i]\n",
    "                    time += 1\n",
    "                    if cutsum*2>= sum0:\n",
    "                        shouldbreak = True\n",
    "                        break\n",
    "            if shouldbreak:\n",
    "                break\n",
    "        return time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heappop, heappush\n",
    "class Solution:\n",
    "    def halveArray(self, nums) :\n",
    "        s1 = sum(nums)\n",
    "        v1 = s1 / 2\n",
    "        new_arr = []\n",
    "        \n",
    "        v2 = 0\n",
    "        ans = 0\n",
    "        for item in nums:\n",
    "            heappush(new_arr, -item)\n",
    "        \n",
    "        while v2 < v1:\n",
    "            item = -1 * heappop(new_arr)\n",
    "            v2 += item / 2\n",
    "            heappush(new_arr, -1 * item / 2)\n",
    "            ans += 1\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        s = 0\n",
    "        h = []\n",
    "        for n in nums:\n",
    "            s += n\n",
    "            heapq.heappush(h, -n)\n",
    "\n",
    "        opts = 0\n",
    "        target = s / 2\n",
    "        while s > target:\n",
    "            n = h[0] / 2\n",
    "            heapq.heapreplace(h, n)\n",
    "            s += n\n",
    "            opts += 1\n",
    "        return opts\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        s = sum(nums) / 2\n",
    "        h = []\n",
    "        for v in nums:\n",
    "            heappush(h, -v)\n",
    "        ans = 0\n",
    "        while s > 0:\n",
    "            t = -heappop(h) / 2\n",
    "            s -= t\n",
    "            heappush(h, -t)\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        pq = []\n",
    "        for x in nums:\n",
    "            heappush(pq, -x)\n",
    "        ans = 0\n",
    "        sumv1 = sum(nums)\n",
    "        sumv2 = sumv1 / 2\n",
    "        while sumv1 > sumv2:\n",
    "            tmp = -heappop(pq)\n",
    "            sumv1 -= tmp / 2\n",
    "            heappush(pq, -(tmp / 2))\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        ans = -sum(nums)/2\n",
    "        nums = [-num for num in nums]\n",
    "        heapq.heapify(nums)\n",
    "        i = 0\n",
    "\n",
    "        while res > ans:\n",
    "            print(ans,res)\n",
    "            i+=1\n",
    "            temp = heapq.heappop(nums)\n",
    "            res += temp/2\n",
    "            heapq.heappush(nums,temp/2)\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# from sortedlistcontainers import SortedList\n",
    "# class Solution:\n",
    "#     def halveArray(self, nums: List[int]) -> int:\n",
    "#         t = sum(nums) / 2\n",
    "#         arr = SortedList(nums)\n",
    "#         cnt = 0\n",
    "#         c = 0\n",
    "#         while c < t:\n",
    "#             c += arr[-1] / 2\n",
    "#             arr[-1] /= 2\n",
    "#             cnt += 1\n",
    "#         return cnt\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        nums = SortedList(nums)\n",
    "        Sum = sum(nums)\n",
    "        total = 0\n",
    "        cnt = 0\n",
    "        while total < Sum / 2:\n",
    "            last = nums.pop(-1)\n",
    "            nums.add(last / 2)\n",
    "            total += (last / 2)\n",
    "            cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        pq=[]\n",
    "        for num in nums:\n",
    "            heappush(pq, -num)\n",
    "        res=0\n",
    "        remain=sum(nums)/2\n",
    "        while remain>0:\n",
    "            x=-heappop(pq)\n",
    "            remain-=x/2\n",
    "            heappush(pq, -(x/2))\n",
    "            res+=1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        h = []\n",
    "        sum1 = sum(nums)\n",
    "        for num in nums:\n",
    "            heappush(h,-num)\n",
    "        \n",
    "        sum2 = 0\n",
    "        while sum2 < sum1/2:\n",
    "            x = -heappop(h)\n",
    "            sum2 += x/2\n",
    "            heappush(h,-(x/2))\n",
    "            res += 1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        summ = sum(nums)\n",
    "        heap = [-i for i in nums]\n",
    "        heapq.heapify(heap)\n",
    "        reduced = 0\n",
    "        num = 0\n",
    "        while reduced < summ / 2:\n",
    "            a = -heapq.heappop(heap)\n",
    "            print(a)\n",
    "            a /= 2\n",
    "            reduced += a\n",
    "            num += 1\n",
    "            print(-a)\n",
    "            heapq.heappush(heap, -a)\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def halveArray(self, nums: List[int]) -> int:\n",
    "#         # \n",
    "#         s0 = 0.5*sum(nums)\n",
    "#         nums = [-num for num in nums]\n",
    "#         heapify(nums)\n",
    "#         k = 0\n",
    "#         while True:\n",
    "#             heapreplace(nums, nums[0]/2)\n",
    "#             k += 1\n",
    "#             if -sum(nums) <= s0:\n",
    "#                 break\n",
    "#         return k\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        pq = []\n",
    "        for num in nums:\n",
    "            heappush(pq, -num)\n",
    "        res = 0\n",
    "        sum1 = sum(nums)\n",
    "        sum2 = 0\n",
    "        while sum2 < sum1 / 2:\n",
    "            x = -heappop(pq)\n",
    "            sum2 += x / 2\n",
    "            heappush(pq, -(x / 2))\n",
    "            res += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        # 每次选择最大的数字即可\n",
    "        heap = [-i for i in nums]\n",
    "        heapify(heap)\n",
    "        n = sum(nums) / 2\n",
    "        ans = 0\n",
    "        while n > 0:\n",
    "            tmp = heappop(heap) / 2\n",
    "            # print(tmp)\n",
    "            n += tmp\n",
    "            heappush(heap, tmp)\n",
    "            ans += 1\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        s = sum(nums)\n",
    "        queue = []\n",
    "        for i in nums:\n",
    "            heappush(queue,-i)\n",
    "        maxnum = 0\n",
    "        count = 0\n",
    "        temp = 0\n",
    "        while temp < s/2:\n",
    "            maxnum = -heappop(queue) * 0.5\n",
    "            heappush(queue,-maxnum)\n",
    "            count += 1\n",
    "            temp += maxnum\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        pq = []\n",
    "        for num in nums:\n",
    "            heappush(pq,-num)\n",
    "        res = 0\n",
    "        sum1 = sum(nums)\n",
    "        sum2 = 0\n",
    "        while sum2 < sum1 / 2:\n",
    "            x = -heappop(pq)\n",
    "            sum2 += x / 2\n",
    "            heappush(pq,-(x / 2))\n",
    "            res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        num_sum = sum(nums)\n",
    "        ans_sum = 0\n",
    "        hq = []\n",
    "        for num in nums:\n",
    "            heapq.heappush(hq, -num)\n",
    "\n",
    "        while ans_sum < num_sum / 2:\n",
    "            v = -heapq.heappop(hq)\n",
    "            ans_sum += v / 2\n",
    "            heapq.heappush(hq, -(v / 2))\n",
    "            res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        summ = sum(nums)\n",
    "        heap = [-i for i in nums]\n",
    "        heapq.heapify(heap)\n",
    "        reduced = 0\n",
    "        num = 0\n",
    "        while reduced < summ / 2:\n",
    "            a = -heapq.heappop(heap)\n",
    "            # print(a)\n",
    "            a /= 2\n",
    "            reduced += a\n",
    "            num += 1\n",
    "            # print(-a)\n",
    "            heapq.heappush(heap, -a)\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int or float]) -> int:\n",
    "        half_num = sum(nums) / 2\n",
    "        sorted_nums = sorted(nums, reverse=True)\n",
    "        operate_times = 0\n",
    "        new_nums = []\n",
    "        index = 0\n",
    "        while index < len(sorted_nums):\n",
    "            operate_times += 1\n",
    "            if len(new_nums) and sorted_nums[index] < new_nums[0]:\n",
    "                sorted_nums.insert(index, new_nums[0])\n",
    "                new_nums = new_nums[1:]\n",
    "\n",
    "            half_item = sorted_nums[index] / 2\n",
    "            if half_num - half_item <= 0:\n",
    "                return operate_times\n",
    "\n",
    "            half_num -= half_item\n",
    "            new_nums.append(half_item)\n",
    "            index += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def halveArray(self, nums: List[int]) -> int:\r\n",
    "        # nums.sort(reverse=True)\r\n",
    "        # the_sum = sum(nums)\r\n",
    "        # half_of_sum = the_sum / 2\r\n",
    "        # count = 0\r\n",
    "        # while the_sum > half_of_sum:\r\n",
    "        #     cur_max = nums[0]\r\n",
    "        #     half_of_max = cur_max / 2\r\n",
    "        #     the_sum = the_sum - half_of_max\r\n",
    "        #     count += 1\r\n",
    "        #     # 更新数组为有序\r\n",
    "        #     i = 0\r\n",
    "        #     while nums[i] >= half_of_max and i < len(nums) - 1:\r\n",
    "        #         nums[i] = nums[i+1]\r\n",
    "        #         i += 1\r\n",
    "        #     nums[i-1] = half_of_max\r\n",
    "\r\n",
    "        # return count\r\n",
    "\r\n",
    "        # *******************************************************************\r\n",
    "\r\n",
    "        for i in range(len(nums)):\r\n",
    "            nums[i] = - (nums[i] << 20)\r\n",
    "\r\n",
    "        heapq.heapify(nums)\r\n",
    "        half, count = sum(nums) >> 1, 0\r\n",
    "\r\n",
    "        while half < 0:\r\n",
    "            half = half - (nums[0] >> 1)\r\n",
    "            heapq.heapreplace(nums, nums[0] >> 1)\r\n",
    "            count += 1\r\n",
    "        \r\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halveArray(self, nums: List[int]) -> int:\n",
    "        pq = []\n",
    "        for num in nums:\n",
    "            heappush(pq, -num)\n",
    "        res = 0\n",
    "        sum1 = sum(nums)\n",
    "        sum2 = 0\n",
    "        while sum2 < sum1 / 2:\n",
    "            x = -heappop(pq)\n",
    "            sum2 += x / 2\n",
    "            heappush(pq, -(x / 2))\n",
    "            res += 1\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
